//
//  99_恢复二叉搜索树.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/13.
/**
 https://leetcode.cn/problems/recover-binary-search-tree/description/
 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
 */

import UIKit

class SetRecoverTree: NSObject {
    var prev: TreeNode<Int>? // 前一个遍历的节点
    var first: TreeNode<Int>? // 逆序对大的节点
    var second: TreeNode<Int>? // 逆序对小的节点
    func recoverTree(_ root: TreeNode<Int>?) {
        getNode(root)
        if let first = first,
           let second = second {
            let temp = first.val
            first.val = second.val
            second.val = temp

        }
        
    }
    
    func getNode(_ node: TreeNode<Int>?) {
        guard let node = node else {
            return
        }
        getNode(node.left)
        
        if let prev = prev, prev.val > node.val {
            if first == nil {
                first = prev
            }
            second = node
        }
        prev = node
        getNode(node.right)
    }
}
